区间dp

一.概念

对于一段区间求最优解,且该区间可以分为几个小区间的最优解合并(最优子结构)。

二.基本思路

阅读全文 »

伯努利数

伯努利数是一个用于解决 nn 次方和的数列。

它的递归定义公式如下:

i=0n(n+1i)Bi=[n=0]        (1.1)\sum_{i=0}^n \binom {n+1}{i} B_i=[n=0] ~~~~~~~~ (1.1)

阅读全文 »

P6825 「EZEC-4」求和

i=1nj=1ngcd(i,j)i+j\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)^{i+j}

d=1ni=1nj=1n[gcd(i,j)=d]di+j\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n [\gcd(i,j)=d]d^{i+j}

阅读全文 »

CF547C Mike and Foam

cic_iii 毫升泡沫的酒在架子上的瓶数,A=maxi=1naiA=\max_{i=1}^n a_i

为了方便将二元组视为有序,答案除以 22 即可。

i=1Aj=1Acicj[gcd(i,j)=1]\sum_{i=1}^A \sum_{j=1}^A c_i c_j [\gcd(i,j)=1]

阅读全文 »

CF439E Devu and Birthday Celebration

i1=1ni2=1n...if=1n[ai=n][gcdai=1]\sum_{i_1=1}^n\sum_{i_2=1}^n...\sum_{i_f=1}^n [\sum{a_i}=n][\gcd{a_i}=1]

i1=1ni2=1n...if=1n[ai=n]dgcdaiμ(d)\sum_{i_1=1}^n\sum_{i_2=1}^n...\sum_{i_f=1}^n [\sum{a_i}=n]\sum_{d|\gcd{a_i}} \mu(d)

阅读全文 »